﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace InformationRetrieval.Wildcard
{
    /// <summary>
    /// Implements a permuterm index, which allows for efficient wildcard queries.
    /// Usage:
    /// 1. Create a new instance of the permuterm index
    /// 2. Add an arbitrary number of terms to the index
    /// 3. Search the index with a wildcard query
    ///     -> it will return all the terms added in step 2 which match the query.
    /// </summary>
    public class PermutermIndex : IWildcardIndex
    {
        #region Fields
        SortedSet<string> _rotatedTerms = new SortedSet<string>(); 
        #endregion

        #region Add terms to index
        /// <summary>
        /// Adds a term to the index.
        /// </summary>
        /// <param name="term">The term to be added</param>
        public void AddTerm(string term)
        {
            foreach (var rotation in GenerateRotations(term.ToLower()))
            {
                _rotatedTerms.Add(rotation);
            }
        }

        /// <summary>
        /// Adds each term in the sequence to the index.
        /// </summary>
        /// <param name="terms">A sequence of terms</param>
        public void AddTerms(IEnumerable<string> terms)
        {
            foreach (var term in terms)
            {
                AddTerm(term);
            }
        }
        #endregion

        #region Find terms in index
        /// <summary>
        /// Finds all terms in the index that match the query. The query
        /// must be a single term, i.e. it can not contain white-space characters.
        /// The query may contain an arbitrary number of wildcards '*'. 
        /// </summary>
        /// <param name="query">Query string</param>
        /// <returns>A sequence of terms that match the query</returns>
        public IEnumerable<string> Find(string query)
        {
            if (query.Contains(' '))
                throw new ArgumentException("Query string must be a single term without white space characters");

            if (query.Contains('*'))
                return FindWithWildcard(query);
            else return new[] { query };
        }

        /// <summary>
        /// Finds all terms in the index that match the query string. 
        /// The query string may contain an arbitrary number of wildcards '*'. 
        /// </summary>
        /// <param name="query">Query string with wildcards</param>
        /// <returns>A sequence of terms that match the query string</returns>
        private IEnumerable<string> FindWithWildcard(string query)
        {
            // Rotate and truncate the query to make an index lookup possible
            string rotatedQuery = GetQueryString(query);

            // First string in the index that shouldn't match anymore
            // e.g. if query is 'aaa*', upperBound would be 'aab'
            string upperBound = rotatedQuery.Substring(0, rotatedQuery.Length - 1) + (char)(rotatedQuery[rotatedQuery.Length - 1] + 1);

            // Get all entries that could possibly match the query. 
            // SortedSet<> internally uses a red-black tree and is therefore quite fast
            SortedSet<string> results = _rotatedTerms.GetViewBetween(rotatedQuery, upperBound);

            // Remove duplicates and false positives, i.e. results that do not 
            // match the query but made it into the result list because a 
            // permuterm index can't apply multiple wildcards correctly.
            return (from r in results
                    let ur = Unrotate(r)
                    where WildcardTools.MatchWildcard(ur, query) 
                    select ur).Distinct();
        }
        #endregion

        #region Helper Methods
        /// <summary>
        /// Appends a dollar sign '$' to the term and returns all possible
        /// rotations. E.g. if the term is 'abc', it returns 'abc$', '$abc', 
        /// 'c$ab' and 'bc$a'.
        /// </summary>
        /// <param name="term">A term (without dollar sign)</param>
        /// <returns>Sequence of all possible rotations</returns>
        private IEnumerable<string> GenerateRotations(string term)
        {
            term = term + "$";
            for (int i = 0; i < term.Length; i++)
                yield return term.Substring(i) + term.Substring(0, i);
        }

        /// <summary>
        /// Takes a rotated term that was produced be the method 'GenerateRotations'
        /// and returns the original, non-rotated term. 
        /// </summary>
        /// <param name="rotatedTerm">Rotated term, containing a dollar sign</param>
        /// <returns>Non-rotated term, without the dollar sign</returns>
        private string Unrotate(string rotatedTerm)
        {
            if (rotatedTerm[rotatedTerm.Length - 1] == '$') return rotatedTerm.Substring(0, rotatedTerm.Length - 1);

            int dollarIndex = rotatedTerm.IndexOf('$');
            return rotatedTerm.Substring(dollarIndex + 1) + rotatedTerm.Substring(0, dollarIndex);
        }

        /// <summary>
        /// Rotates and truncates the query to make an index lookup possible.
        /// Specifically, the query is rotated until the first asterisk in the
        /// query becomes the last letter, then the query is truncated until it
        /// contains no more asterisks. 
        /// </summary>
        /// <param name="query"></param>
        /// <returns></returns>
        private string GetQueryString(string query)
        {
            query = query + "$";

            string rotatedQuery;
            if (query.StartsWith("*"))
            {
                // query starts with '*' -> special case
                rotatedQuery = query.Substring(1) + "*";
            }
            else
            {
                // rotate query
                string first = query.Substring(0, query.IndexOf('*'));
                string last = query.Substring(query.LastIndexOf('*') + 1);
                rotatedQuery = last + first + "*";
            }

            // truncate query
            string[] tokens = rotatedQuery.Split(new[] { '*' }, StringSplitOptions.RemoveEmptyEntries);
            return tokens[0];
        }


        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();

            foreach (var term in _rotatedTerms)
            {
                sb.AppendLine(term);
            }


            return sb.ToString();
        }
        #endregion
    }
}
